package leetcode_core.leetcode_3;

import java.util.Arrays;
import java.util.Comparator;

public class VideoStitching {
    public int videoStitching(int[][] clips, int time) {
        //1.排序:按照起点进行排序,从小到大
        Arrays.sort(clips, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0] - o2[0];
            }
        });
        //2.依据规律来进行区间的合并
        int ans = 0;//选择的短视频个数
        int curEnd = 0;//curEnd表示的是已选择的视频片段的所构成的片段的终点
        int nextEnd = 0;//一开始啥也没选,必然是0
        int i = 0;
        while (i<clips.length && clips[i][0] <= curEnd){
            while (i<clips.length && clips[i][0] <= curEnd){
                nextEnd = Math.max(nextEnd,clips[i][1]);
            }
            curEnd = nextEnd;
            ans++;
            if(curEnd >= time){
                return ans;
            }
        }
        return -1;
    }

}
